#
# @lc app=leetcode.cn id=5687 lang=python3
#
# [5687] 执行乘法运算的最大分数
#

# @lc code=start
from typing import List
class Solution:
    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:
        dp = [0]
        n = len(multipliers)
        m = len(nums)
        for k in range(1,n+1):
            tmp = [0]*(k+1)
            for i in range(1, k+1):
                print(n, k, i)
                tmp[i] = dp[i-1]+multipliers[k-1]*nums[i-1]
                if i<k:
                    tmp[i] = max(tmp[i], dp[i]+multipliers[k-1]*nums[m+i-k])
            dp = tmp
        return max(dp)
# @lc code=end

if __name__=='__main__':
    nums = [1,2,3]
    multipliers = [3,2,1]
    solution = Solution()
    print(solution.maximumScore(nums, multipliers))